﻿// 10197. 「一本通 6.2 例 1」Prime Distance.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>
#include <climits>

using namespace std;

/*
https://loj.ac/p/10197

题目描述
原题来自：Waterloo local，题面详见 POJ 2689

给定两个整数 L,R，求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。

输入格式
多组数据。每行两个数 L,R。

输出格式
详见输出样例。

2 17
14 17

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

数据范围与提示
对于全部数据，1<= L< R< 2^{31},R-L<= 10^6。
*/

const int N = 100000;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
long long range[1000010];
long long l, r;
int res[1000010], rescnt = 0;


void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}


void solve() {
    memset(range, 0, sizeof range);
    if (l == 1)l = 2;
    for (int i = 0; i <= r - l; i++) {
        range[i] = l + i;
    }
    for (int i = 0; i < cnt; i++) {
        long long currPrime = primes[i];
        if (currPrime * currPrime > r) break;
        //找到l~~r中第一个 prime的倍数
        long long first = l;
        if (first % currPrime ==0) {
            first = max(first, currPrime + currPrime);
        }
        else {
            first = currPrime - l % currPrime + l;
            first = max(first, currPrime + currPrime);
        }
        for (long long j = first; j <= r; j += currPrime) {
            range[j-l] = 0;
        }
    }
    rescnt = 0;
    for (int i = 0; i <= r - l; i++) {
        if (range[i] != 0) {
            res[rescnt] = range[i]; rescnt++;
        }
    }

    //检查
    int minv = INT_MAX; int minidx = -1;
    int maxv = INT_MIN; int maxidx = -1;

    for (int i = 0; i < rescnt - 1; i++) {
        if (res[i + 1] - res[i] < minv) {
            minv = res[i + 1] - res[i];
            minidx = i;
        }
        if (res[i + 1] - res[i] > maxv) {
            maxv = res[i + 1] - res[i];
            maxidx = i;
        }
    }

    if (minidx == -1 || -1 == maxidx) {
        cout << "There are no adjacent primes." << endl;
    }
    else {
        int a = res[minidx], b = res[minidx + 1];
        int c = res[maxidx], d = res[maxidx + 1];
        cout << a << "," << b << " are closest, " << c << "," << d << " are most distant." << endl;
    }

    return;
}


int main()
{
    get_primes(100000);
    while (cin >> l >> r) {
        solve();
    }
    return 0;
}

 